import java.util.*;

/**
 * 题目：靠谱的车
 * 
 * 题目描述：
 * 程序员小明坐出租车上班，发现出租车计价器有问题，总是显示更高的车费。
 * 出租车司机解释说，他不喜欢数字'4'，所以修改了计价器。
 * 任何原本应该显示'4'的数字位置都会被直接跳过，其他功能保持正常。
 * 
 * 例如：
 * 1. 如果计价器显示23，加1后变成25（跳过24）
 * 2. 如果计价器显示39，加1后变成50（跳过40-49）
 * 3. 如果计价器显示399，加1后变成500（跳过400-499）
 * 
 * 小明看穿了司机的把戏，计划用自己的知识来击败司机的计谋。
 * 给定计价器上显示的读数，返回实际产生的费用。
 * 
 * 输入描述：
 * 只有一行，包含一个数字N，表示计价器上的读数。
 * 约束：(1 <= N <= 888,888,888)
 * 
 * 输出描述：
 * 一个数字，表示实际产生的费用。以换行符结尾。
 * 
 * 示例1：
 * 输入：5
 * 输出：4
 * 
 * 示例2：
 * 输入：17
 * 输出：15
 * 
 * 示例3：
 * 输入：100
 * 输出：81
 * 
 * 解题思路：
 * 这是一个进制转换问题，需要将包含'4'的数字转换为不包含'4'的数字。
 * 实际上是将"九进制"数字转换为十进制数字。
 * 
 * 算法分析：
 * - 时间复杂度：O(log N)
 * - 空间复杂度：O(log N)
 * - 算法类型：进制转换，数学计算
 */
public class ReliableTaxi {
    
    /**
     * 方法1：九进制转换法（推荐使用）
     * 将计价器读数当作九进制数字转换为十进制
     * 
     * 算法思路：
     * 1. 将数字N当作九进制数字处理
     * 2. 将九进制数字转换为十进制
     * 3. 如果某位数字>=4，则减1（因为跳过了4）
     * 
     * 时间复杂度：O(log N)
     * 空间复杂度：O(1)
     */
    public static long actualCost1(long n) {
        long result = 0;
        long base = 1;
        
        while (n > 0) {
            long digit = n % 10;
            if (digit > 4) {
                digit--; // 跳过数字4
            }
            result += digit * base;
            base *= 9; // 九进制
            n /= 10;
        }
        
        return result;
    }
    
    /**
     * 方法2：字符串处理法
     * 将数字转换为字符串进行处理
     * 
     * 算法思路：
     * 1. 将数字转换为字符串
     * 2. 逐位处理，将>=4的数字减1
     * 3. 将处理后的字符串转换为九进制数字
     * 
     * 时间复杂度：O(log N)
     * 空间复杂度：O(log N)
     */
    public static long actualCost2(long n) {
        String str = String.valueOf(n);
        StringBuilder sb = new StringBuilder();
        
        for (char c : str.toCharArray()) {
            int digit = c - '0';
            if (digit > 4) {
                digit--; // 跳过数字4
            }
            sb.append(digit);
        }
        
        // 将处理后的字符串当作九进制转换为十进制
        return Long.parseLong(sb.toString(), 9);
    }
    
    /**
     * 方法3：数学计算法
     * 使用数学公式直接计算
     * 
     * 算法思路：
     * 1. 将数字N的每一位数字提取出来
     * 2. 如果数字>=4，则减1
     * 3. 使用九进制转换公式计算
     * 
     * 时间复杂度：O(log N)
     * 空间复杂度：O(log N)
     */
    public static long actualCost3(long n) {
        List<Integer> digits = new ArrayList<>();
        
        // 提取各位数字
        while (n > 0) {
            int digit = (int)(n % 10);
            if (digit > 4) {
                digit--; // 跳过数字4
            }
            digits.add(digit);
            n /= 10;
        }
        
        // 计算九进制值
        long result = 0;
        long base = 1;
        for (int digit : digits) {
            result += digit * base;
            base *= 9;
        }
        
        return result;
    }
    
    /**
     * 方法4：递归转换法
     * 使用递归方式处理数字转换
     * 
     * 算法思路：
     * 1. 递归处理数字的每一位
     * 2. 如果当前位>=4，则减1
     * 3. 递归处理剩余位数
     * 
     * 时间复杂度：O(log N)
     * 空间复杂度：O(log N) 递归栈
     */
    public static long actualCost4(long n) {
        if (n == 0) return 0;
        
        long digit = n % 10;
        if (digit > 4) {
            digit--; // 跳过数字4
        }
        
        return digit + 9 * actualCost4(n / 10);
    }
    
    /**
     * 方法5：位运算优化法
     * 使用位运算优化计算过程
     * 
     * 算法思路：
     * 1. 使用位运算快速处理数字
     * 2. 优化九进制转换过程
     * 3. 减少乘法和除法运算
     * 
     * 时间复杂度：O(log N)
     * 空间复杂度：O(1)
     */
    public static long actualCost5(long n) {
        long result = 0;
        long base = 1;
        
        while (n > 0) {
            long digit = n & 0xF; // 取最低4位
            if (digit > 4) {
                digit--; // 跳过数字4
            }
            result += digit * base;
            base *= 9;
            n >>= 4; // 右移4位，处理下一位
        }
        
        return result;
    }
    
    /**
     * 辅助方法：验证结果
     * 通过反向计算验证结果的正确性
     */
    public static boolean verifyResult(long original, long actual) {
        // 将actual转换为计价器显示的数字
        long display = 0;
        long base = 1;
        long temp = actual;
        
        while (temp > 0) {
            long digit = temp % 9;
            if (digit >= 4) {
                digit++; // 恢复被跳过的4
            }
            display += digit * base;
            base *= 10;
            temp /= 9;
        }
        
        return display == original;
    }
    
    /**
     * 主方法 - 程序入口
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        System.out.println("请输入计价器显示的读数N：");
        long n = scanner.nextLong();
        
        // 测试所有方法
        System.out.println("\n=== 所有算法结果对比 ===");
        
        long result1 = actualCost1(n);
        long result2 = actualCost2(n);
        long result3 = actualCost3(n);
        long result4 = actualCost4(n);
        long result5 = actualCost5(n);
        
        System.out.println("方法1（九进制转换法）: " + result1);
        System.out.println("方法2（字符串处理法）: " + result2);
        System.out.println("方法3（数学计算法）: " + result3);
        System.out.println("方法4（递归转换法）: " + result4);
        System.out.println("方法5（位运算优化法）: " + result5);
        
        // 验证结果
        System.out.println("\n=== 结果验证 ===");
        System.out.println("方法1验证: " + verifyResult(n, result1));
        System.out.println("方法2验证: " + verifyResult(n, result2));
        System.out.println("方法3验证: " + verifyResult(n, result3));
        System.out.println("方法4验证: " + verifyResult(n, result4));
        System.out.println("方法5验证: " + verifyResult(n, result5));
        
        // 推荐使用的方法
        System.out.println("\n推荐使用方法1（九进制转换法），逻辑最清晰，效率最高");
        
        scanner.close();
    }
}
